package 每日一题;

public class No424替换后的最长重复字符 {

    /**
     * 给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，
     * 总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
     * 注意：字符串长度 和 k 不会超过 104。
     *
     * 示例 1：
     * 输入：s = "ABAB", k = 2
     * 输出：4
     * 解释：用两个'A'替换为两个'B',反之亦然。
     * 示例 2：
     * 输入：s = "AABABBA", k = 1
     * 输出：4
     * 解释：
     * 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
     * 子串 "BBBB" 有最长重复字母, 答案为 4。
     */

    //GOOD
    public int characterReplacement(String s, int k) {
        if (s == null) {
            return 0;
        }
        int[] map = new int[26];
        char[] chars = s.toCharArray();
        int left = 0;
        int right = 0;
        int historyCharMax = 0;
        while (right<s.length()){
            int index = chars[right] - 'A';
            map[index]++;
            historyCharMax = Math.max(historyCharMax, map[index]);
            if (right - left  >= historyCharMax + k) {
                map[chars[left] - 'A']--;
                left++;
            }
            right++;
        }
        return right - left;
    }

    //低级题版:求最长重复子串
    public int characterLower(String s){

        int left=0;
        int right=0;
        int max=0;

        while (right<s.length()){

            int count=0;
            while (right<s.length()&&s.charAt(left)==s.charAt(right)){
                count++;
                right++;
            }
            max=Math.max(count,max);
            left=right;
        }

        return max;
    }

    //低级版:求最长重复子串(保持窗口不变来做
    public int characterLower2(String s){

        int left=0;
        int right=0;
        int max=0;
        int[] map=new int[26];

        while (right<s.length()){

//            int lastMax=max;
            int currentCount=++map[s.charAt(right)-'A'];
            max=Math.max(currentCount,max);//窗口进入了当前字符

            if(right-left>=max){
                //最大长度没有变,就整体右移
                map[s.charAt(left)-'A']--;
                left++;
                right++;//right为什么要++呢?因为框的大小就是最长重复字符的长度!!!
            }else{
                right++;
            }

//            if(max<lastMax){
//                //不可能
//                throw new RuntimeException("不可能");
//            }else if(max>lastMax){
//                //加入了更长的字符
//                right++;//这里能理解
//            }else{
//                //只能等于,吐出
//                map[s.charAt(left)-'A']--;
//                left++;
//                right++;//right为什么要++呢?因为框的大小就是最长重复字符的长度!!!
//            }

        }

        return right-left;
    }

    public static void main(String[] args) {
        No424替换后的最长重复字符 n=new No424替换后的最长重复字符();
        String str="ACBDSSSABAA";
//        int result = n.characterReplacement(str, 1);
//        System.out.println(result);
        int result2 = n.characterLower2(str);
        System.out.println(result2);
    }

}
